package com.arceus.leetcode;

/**
 * @author : iron
 * @version : 1.0.0
 * @date : 11:33 AM 2019/2/28
 */

public class t807 {

    public static int maxIncreaseKeepingSkyline(int[][] grid) {
        int sum = 0;
        for (int b = 0; b < grid.length; b++) {
            for (int a = 0; a < grid.length; a++) {
                int max = 0;
                int max1 = 0;
                int max2 = 0;
                for (int i = 0; i < grid.length; i++) {
                    if (grid[b][i] > max1) {
                        max1 = grid[b][i];
                    }
                    if (grid[i][a] > max2) {
                        max2 = grid[i][a];
                    }
                }
                max = max1 > max2 ? max2 : max1;
                sum += max > grid[b][a] ? max - grid[b][a] : 0;
            }
        }
        return sum;
    }

    /**
     * 优化后的解法
     * @param grid
     * @return
     */
    public static int maxIncreaseKeepingSkyline2(int[][] grid) {
        int max[] = new int[grid.length];
        int max2[] = new int[grid[0].length];

        for (int a = 0; a < grid.length; a++) {
            max[a] = grid[a][0];
            for (int b = 1; b < grid[0].length; b++) {
                max[a] = grid[a][b] > max[a] ? grid[a][b] : max[a];
            }
        }

        for (int b = 0; b < grid.length; b++) {
            max2[b] = grid[0][b];
            for (int c = 1; c < grid[0].length; c++) {
                max2[b] = grid[c][b] > max2[b] ? grid[c][b] : max2[b];
            }
        }

        int sum = 0;
        for (int b = 0; b < grid.length; b++) {
            for (int a = 0; a < grid.length; a++) {

                int min = max[b] > max2[a] ? max2[a] : max[b];
                sum += grid[b][a] < min ? min - grid[b][a] : 0;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[][] arr = new int[][]{{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0}};
        maxIncreaseKeepingSkyline2(arr);

    }
}
